/*
 * Copyright (c) 2005, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package com.sun.imageio.plugins.common;

import java.io.PrintStream;

/**
 * General purpose LZW String Table.
 * Extracted from GIFEncoder by Adam Doppelt
 * Comments added by Robin Luiten
 * <code>expandCode</code> added by Robin Luiten
 * The strLen table to give quick access to the lenght of an expanded
 * code for use by the <code>expandCode</code> method added by Robin.
 **/
public class LZWStringTable {

  /**
   * codesize + Reserved Codes
   */
  private final static int RES_CODES = 2;

  private final static short HASH_FREE = (short) 0xFFFF;
  private final static short NEXT_FIRST = (short) 0xFFFF;

  private final static int MAXBITS = 12;
  private final static int MAXSTR = (1 << MAXBITS);

  private final static short HASHSIZE = 9973;
  private final static short HASHSTEP = 2039;

  byte[] strChr;  // after predecessor character
  short[] strNxt;  // predecessor string
  short[] strHsh;  // hash table to find  predecessor + char pairs
  short numStrings;  // next code if adding new prestring + char

  /*
   * each entry corresponds to a code and contains the length of data
   * that the code expands to when decoded.
   */
  int[] strLen;

  /*
   * Constructor allocate memory for string store data
   */
  public LZWStringTable() {
    strChr = new byte[MAXSTR];
    strNxt = new short[MAXSTR];
    strLen = new int[MAXSTR];
    strHsh = new short[HASHSIZE];
  }

  /*
   * @param index value of -1 indicates no predecessor [used in initialisation]
   * @param b the byte [character] to add to the string store which follows
   * the predecessor string specified the index.
   * @return 0xFFFF if no space in table left for addition of predecesor
   * index and byte b. Else return the code allocated for combination index + b.
   */
  public int addCharString(short index, byte b) {
    int hshidx;

    if (numStrings >= MAXSTR) { // if used up all codes
      return 0xFFFF;
    }

    hshidx = hash(index, b);
    while (strHsh[hshidx] != HASH_FREE) {
      hshidx = (hshidx + HASHSTEP) % HASHSIZE;
    }

    strHsh[hshidx] = numStrings;
    strChr[numStrings] = b;
    if (index == HASH_FREE) {
      strNxt[numStrings] = NEXT_FIRST;
      strLen[numStrings] = 1;
    } else {
      strNxt[numStrings] = index;
      strLen[numStrings] = strLen[index] + 1;
    }

    return numStrings++; // return the code and inc for next code
  }

  /*
   * @param index index to prefix string
   * @param b the character that follws the index prefix
   * @return b if param index is HASH_FREE. Else return the code
   * for this prefix and byte successor
   */
  public short findCharString(short index, byte b) {
    int hshidx, nxtidx;

    if (index == HASH_FREE) {
      return (short) (b & 0xFF);    // Rob fixed used to sign extend
    }

    hshidx = hash(index, b);
    while ((nxtidx = strHsh[hshidx]) != HASH_FREE) { // search
      if (strNxt[nxtidx] == index && strChr[nxtidx] == b) {
        return (short) nxtidx;
      }
      hshidx = (hshidx + HASHSTEP) % HASHSIZE;
    }

    return (short) 0xFFFF;
  }

  /*
   * @param codesize the size of code to be preallocated for the
   * string store.
   */
  public void clearTable(int codesize) {
    numStrings = 0;

    for (int q = 0; q < HASHSIZE; q++) {
      strHsh[q] = HASH_FREE;
    }

    int w = (1 << codesize) + RES_CODES;
    for (int q = 0; q < w; q++) {
      addCharString((short) 0xFFFF, (byte) q); // init with no prefix
    }
  }

  static public int hash(short index, byte lastbyte) {
    return ((int) ((short) (lastbyte << 8) ^ index) & 0xFFFF) % HASHSIZE;
  }

  /*
   * If expanded data doesn't fit into array only what will fit is written
   * to buf and the return value indicates how much of the expanded code has
   * been written to the buf. The next call to expandCode() should be with
   * the same code and have the skip parameter set the negated value of the
   * previous return. Succesive negative return values should be negated and
   * added together for next skip parameter value with same code.
   *
   * @param buf buffer to place expanded data into
   * @param offset offset to place expanded data
   * @param code the code to expand to the byte array it represents.
   * PRECONDITION This code must already be in the LZSS
   * @param skipHead is the number of bytes at the start of the expanded code to
   * be skipped before data is written to buf. It is possible that skipHead is
   * equal to codeLen.
   * @return the length of data expanded into buf. If the expanded code is longer
   * than space left in buf then the value returned is a negative number which when
   * negated is equal to the number of bytes that were used of the code being expanded.
   * This negative value also indicates the buffer is full.
   */
  public int expandCode(byte[] buf, int offset, short code, int skipHead) {
    if (offset == -2) {
      if (skipHead == 1) {
        skipHead = 0;
      }
    }
    if (code == (short) 0xFFFF ||    // just in case
        skipHead == strLen[code])  // DONE no more unpacked
    {
      return 0;
    }

    int expandLen;  // how much data we are actually expanding
    int codeLen = strLen[code] - skipHead; // length of expanded code left
    int bufSpace = buf.length - offset;  // how much space left
    if (bufSpace > codeLen) {
      expandLen = codeLen; // only got this many to unpack
    } else {
      expandLen = bufSpace;
    }

    int skipTail = codeLen - expandLen;  // only > 0 if codeLen > bufSpace [left overs]

    int idx = offset + expandLen;   // initialise to exclusive end address of buffer area

    // NOTE: data unpacks in reverse direction and we are placing the
    // unpacked data directly into the array in the correct location.
    while ((idx > offset) && (code != (short) 0xFFFF)) {
      if (--skipTail < 0) { // skip required of expanded data
        buf[--idx] = strChr[code];
      }
      code = strNxt[code];    // to predecessor code
    }

    if (codeLen > expandLen) {
      return -expandLen; // indicate what part of codeLen used
    } else {
      return expandLen;     // indicate length of dat unpacked
    }
  }

  public void dump(PrintStream out) {
    int i;
    for (i = 258; i < numStrings; ++i) {
      out.println(" strNxt[" + i + "] = " + strNxt[i]
          + " strChr " + Integer.toHexString(strChr[i] & 0xFF)
          + " strLen " + Integer.toHexString(strLen[i]));
    }
  }
}
